package 热题100.链表.回文链表_234_简单;
import 链表.两两交换链表中的节点_24.Solution.ListNode;
/*
给你一个单链表的头节点 head ，请你判断该链表是否为
回文链表。如果是，返回 true ；否则，返回 false 。

输入：head = [1,2,2,1]
输出：true

输入：head = [1,2]
输出：false

思路：
    刚开始想的是原链表和翻转的链表进行对比，但是翻转链表之后原链表也变化了，所以只能翻转半个链表
    1. 找到链表的中间位置： 快慢指针，快指针到尾了慢指针正好在中间位置
    2. 翻转后半部链表进行对比
* */
public class Solution {
    public static void main(String[] args) {
        ListNode[] head = new ListNode[4];
        head[3] = new ListNode(1,null);
        head[2] = new ListNode(1,head[3]);
        head[1] = new ListNode(2,head[2]);
        head[0] = new ListNode(1,head[1]);
        System.out.println(isPalindrome(head[0]));
    }

    public static boolean isPalindrome(ListNode head) {
        if (head == null){
            return false;
        }
        // 找到中间位置的尾部
        ListNode firstEnd = findFirstEnd(head);
        ListNode first = head;
        // 翻转后半部链表
        ListNode mid = reverse(firstEnd);
        // 比较
        while (first != null){
            if (first.val != mid.val){
                return false;
            }
            first = first.next;
            mid = mid.next;
        }
        return true;
    }

    // 三个指针来翻转链表
    public static ListNode reverse(ListNode head){
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = null;
        while (cur != null){
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }

    // 快慢指针找链表中间位置
    public static ListNode findFirstEnd(ListNode head){
        ListNode fast = head;
        ListNode slow = head;
        while (fast.next != null && fast.next.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}
